package leetcode.code1606;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
		int len = arrival.length;
		List<Integer> ans = new ArrayList<>();
		// 服务器足够用的时候，所有服务器最多一次。共len个。
		if (len <= k) {
			for (int i = 0; i < len; i++) {
				ans.add(i);
			}
			return ans;
		}
		// 优先级队列int[0] = 完成时间,同时也是可用时间 int[1] = 服务器编号， int[2] = 服务次数
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
		for (int i = 0; i < k; i++) {
			int arr = arrival[i], time = load[i];
			// arr + time时间可用i服务，累计服务1次
			queue.add(new int[] { arr + time, i, 1 });
		}
		int max = 1;// 累计最多服务次数
		TreeMap<Integer, int[]> list = new TreeMap<>();
		for (int i = k; i < len; i++) {
			int arr = arrival[i], time = load[i];
			// 能做就做，不能做就过
			if ((!queue.isEmpty() && queue.peek()[0] <= arr) || !list.isEmpty()) {
				int wanna = i % k;//
				while (!queue.isEmpty() && queue.peek()[0] <= arr) {
					int[] cur = queue.poll();
					list.put(cur[1], cur);
				}
				Map.Entry<Integer, int[]> entry = list.ceilingEntry(wanna);
				if (entry == null) {
					entry = list.firstEntry();
				}
				list.remove(entry.getKey());
				int[] cur = entry.getValue();
				int idx = cur[1], done = cur[2];
				max = Math.max(max, done + 1);
				queue.add(new int[] { arr + time, idx, done + 1 });
//				if (list.size() > 0) {
//					for (int[] info : list.values()) {
//						queue.add(info);
//					}
//				}
			}
		}
		// 拿出累计最多服务次数的服务器号码
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			if (cur[2] == max) {
				ans.add(cur[1]);
			}
		}
		//
		if (!list.isEmpty()) {
			for (int[] cur : list.values()) {
				if (cur[2] == max) {
					ans.add(cur[1]);
				}
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		HelpDebug.compare(HelpDebug.str2array3("[0,1,2]"),
				this.busiestServers(3, HelpDebug.str2array3("[1,2,6,9,10,12]"), HelpDebug.str2array3("[2,4,3,3,11,8]")));
		HelpDebug.compare(HelpDebug.str2array3("[1]"),
				this.busiestServers(3, HelpDebug.str2array3("[1,2,3,4,8,9,10]"), HelpDebug.str2array3("[5,2,10,3,1,2,2]")));
		HelpDebug.compare(HelpDebug.str2array3("[1,2]"),
				this.busiestServers(4, HelpDebug.str2array3("[1,3,4,5,10,12]"), HelpDebug.str2array3("[11,9,3,1,9,12]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
